package ninthweek;

import fourthweek.Array.ArrayUnorderedList;
import fourthweek.UnorderedListADT;
import secondweek.EmptyCollectionException;
import seventhweek.BinaryTreeNode;

public class LinkedHeap<T> extends LinkedBinaryTree<T> implements HeapADT<T> {

    public HeapNode<T> lastNode;

    public LinkedHeap() {
        super();
    }

    @Override
    public void addElement(T obj) {
        // 一个堆结点
        HeapNode<T> node = new HeapNode<T>(obj);

        if (root == null)
            root = node;// 如果为空 就把root指向当前的结点
        else {
            // 获取父结点 把需要添加的父结点返回
            HeapNode<T> nextParent = getNextParentAdd();

            if (nextParent.getLeft() == null)
                nextParent.setLeft(node);
            else
                nextParent.setRight(node);

            node.setParent(nextParent);
        }

        lastNode = node;// 最后的结点的引用
        modCount++;

        if (size() > 1)
            heapifyAdd();

    }

    /**
     * 添加修改当前堆
     */
    private void heapifyAdd() {
        T temp;
        // 获取最后一个结点
        HeapNode<T> next = lastNode;

        // 临时保存
        temp = next.getElement();

        // 如果不是root结点而且小于当前的结点的父结点就进行循环
        while ((next != root)
                && (((Comparable) temp)
                .compareTo(next.getParent().getElement()) < 0)) {

            next.setElement(next.getParent().getElement());
            next = next.parent;
        }
        next.setElement(temp);// 放置到最后的结点

    }

    /**
     * 获取当前需要添加位置的结点的父结点
     *
     * @return
     */
    private HeapNode<T> getNextParentAdd() {

        HeapNode<T> result = lastNode;// 当前的空白结点

        while ((result != root) && (result.getParent().getLeft() != result))
            result = result.getParent();

        if (result != root) {
            // /不是一个满堆
            if (result.getParent().getRight() == null)
                result = result.getParent();
            else {
                result = (HeapNode<T>) result.getParent().getRight();
                // 不断的向下寻找最后的父结点
                while (result.getLeft() != null)
                    result = (HeapNode<T>) result.getLeft();
            }
        } else {// 当前堆是一个满堆
            while (result.getLeft() != null)
                result = (HeapNode<T>) result.getLeft();
        }

        return result;
    }

    @Override
    public T removeMin() throws EmptyCollectionException {
        if (isEmpty())
            throw new EmptyCollectionException("LinkedHeap");

        T minElement = root.getElement();

        if (size() == 1) {
            root = null;
            lastNode = null;
        } else {
            // 获取一个新的尾结点
            HeapNode<T> nextLast = getNewLastNode();

            if (lastNode.getParent().getLeft() == lastNode)
                lastNode.getParent().setLeft(null);
            else
                lastNode.getParent().setRight(null);

            ((HeapNode<T>) root).setElement(lastNode.getElement());

            lastNode = nextLast;
            heapifyRemove();
        }

        modCount++;

        return minElement;
    }

    /**
     * 这里面的规则其实比较简单 就是在描述的时候比较麻烦： 【1】首先我们需要在程序中找到当前的最后一个结点，
     * 【2】然后判断如果当前结点不是根节点，并且是父结点的左孩子，就不断的迭代向上查找；反之终止迭代
     * 【3】然后判断当前结点不是是根节点,就寻找当前结点父结点的左孩子 【4】获取当前结点的右孩子是不是空 如果不为空
     * 迭代一直到result的右孩子为空为止
     *
     * @return
     *
     *         返回最新的最末结点
     */
    private HeapNode<T> getNewLastNode() {
        HeapNode<T> result = lastNode;

        // 非根的右边结点
        while ((result != root) && (result.getParent().getLeft() == result))
            result = result.getParent();

        if (result != root)
            result = (HeapNode<T>) result.getParent().getLeft();

        while (result.getRight() != null)
            result = (HeapNode<T>) result.getRight();

        return result;
    }

    private void heapifyRemove() {

        T temp;
        HeapNode<T> node = (HeapNode<T>) root;//用户遍历的根结点
        HeapNode<T> left = (HeapNode<T>) node.getLeft();
        HeapNode<T> right = (HeapNode<T>) node.getRight();
        HeapNode<T> next;

        if ((left == null) && (right == null))
            next = null;
        else if (right == null)
            next = left;
        else if (((Comparable) left.getElement()).compareTo(right.getElement()) < 0)
            next = left;
        else
            next = right;

        temp = node.getElement();

        while ((next != null)
                && (((Comparable) next.getElement()).compareTo(temp) < 0)) {
            node.setElement(next.getElement());
            node = next;
            left = (HeapNode<T>) node.getLeft();
            right = (HeapNode<T>) node.getRight();

            if ((left == null) && (right == null))
                next = null;
            else if (right == null)
                next = left;
            else if (((Comparable) left.getElement()).compareTo(right
                    .getElement()) < 0)
                next = left;
            else
                next = right;
        }

        node.setElement(temp);

    }

    @Override
    public T findMin() {
        if (isEmpty())
            throw new EmptyCollectionException("LinkedHeap");

        return root.getElement();
    }

    public String toString(){
        UnorderedListADT<BinaryTreeNode<T>> nodes = new ArrayUnorderedList<BinaryTreeNode<T>>();
        UnorderedListADT<Integer> levelList = new ArrayUnorderedList<Integer>();

        BinaryTreeNode<T> current;
        String result = "";
        int printDepth = this.getHeight();
        int possibleNodes = (int) Math.pow(2, printDepth + 1);
        int countNodes = 0;

        nodes.addToRear(root);
        Integer currentLevel = 0;
        Integer previousLevel = -1;
        levelList.addToRear(currentLevel);

        while (countNodes < possibleNodes) {
            countNodes = countNodes + 1;
            current = nodes.removeFirst();
            currentLevel = levelList.removeFirst();
            if (currentLevel > previousLevel) {
                result = result + "\n\n";
                previousLevel = currentLevel;
                for (int j = 0; j < ((Math.pow(2, (printDepth - currentLevel))) - 1); j++)
                    result = result + " ";
            } else {
                for (int i = 0; i < ((Math.pow(2,
                        (printDepth - currentLevel + 1)) - 1)); i++) {
                    result = result + " ";
                }
            }
            if (current != null) {
                result = result + (current.getElement()).toString();
                nodes.addToRear(current.getLeft());
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(current.getRight());
                levelList.addToRear(currentLevel + 1);
            } else {
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                result = result + " ";
            }
        }
        return result;
    }
}
